//
// Created by Criinal Nicole on 2021/5/7.
//

#ifndef GFD_SUBGRAPHMATCH_H
#define GFD_SUBGRAPHMATCH_H

#include "../dataStructure/Graph.h"
#include "VF2.h"
#include <vector>

//    对图进行重排序，将支点放到图的最前面
//    返回一个只包含支点的子图
Graph generateSuppSubGraph(Graph &graph,
                           const std::set<int> &suppList) {

    Graph retGraph, tmpGraph;
    std::map<int, int> vertexMap;
//    std::cout << graph << "\n";

//    retGraph保存支点，tmpGraph保存非支点
//    建立映射
    int offset = 0;
    for (int i = 0; i < graph.size(); ++i) {
        auto &vertex = graph[i];
        if (suppList.find(vertex.getId()) != suppList.end()) {
            retGraph.push_back(vertex);
            vertexMap[i] = retGraph.size() - 1;
        } else {
            tmpGraph.push_back(vertex);
            vertexMap[i] = suppList.size() + offset;
            offset++;
        }
    }
//    将非支点加到retGraph的末端
    for (auto &vertex : tmpGraph) {
        retGraph.push_back(vertex);
    }

//    根据映射更新图
    for (auto &vertex: retGraph) {
        vertex.updateEdges(vertexMap);
    }
    assert(graph.size() == retGraph.size());
    graph = retGraph;

//    仅保留含有支点的点
    retGraph.resize(suppList.size());
    for (auto &vertex:retGraph) {
        std::vector<Edge> tmpEdges;
        for (auto &edge : vertex.inEdges) {
            if (edge.getFromVertex() < retGraph.size()) {
                tmpEdges.push_back(edge);
            }
        }
        vertex.inEdges = tmpEdges;
        tmpEdges.clear();
        for (auto &edge : vertex.outEdges) {
            if (edge.getToVertex() < retGraph.size()) {
                tmpEdges.push_back(edge);
            }
        }
        vertex.outEdges = tmpEdges;
    }
//    std::cout << retGraph << "\n";
    return retGraph;
}

//    对剩下的图进行匹配时使用的pruneCallback
//    检查到已经匹配成功则返回结果
bool nonSuppPruneCheck(Graph &queryGraph,
                       Graph &dataGraph,
                       std::map<int, int> &matchState,
                       bool &suppMatched) {
    return false;
}

//    对剩下的图进行匹配时使用的matchCallback
//    检查到已经匹配成功则将suppMatched改成true
template<typename LiteralCheck>
bool nonSuppMatchCheck(Graph &queryGraph,
                       Graph &dataGraph,
                       std::map<int, int> &matchState,
                       bool &suppMatched,
                       int &suppValue,
                       int &cntSupp,
                       LiteralCheck literalCheck) {
//    std::cout << "matched!" << std::endl;
//    std::cout << "(patternVertex, targetVertex)" << std::endl;
//    for (auto i:matchState) {
//        std::cout << "(" << queryGraph[i.first].getId() << ", "
//                  << dataGraph[i.second].getId() << ")" << std::endl;
//    }
    if (cntSupp >= suppValue)return false;
    if (literalCheck(matchState)) {
        cntSupp++;
        suppMatched = true;
    }
    return cntSupp < suppValue;
}

//    对仅含有支点的子图进行匹配时使用的matchCallback
//    在此函数中继续进行全图的匹配
template<typename LiteralCheck>
bool suppMatchCheck(Graph &queryGraph,
                    Graph &dataGraph,
                    std::map<int, int> &matchState,
                    int &suppValue,
                    int &cntSupp,
                    LiteralCheck literalCheck) {
    if (!literalCheck(matchState))
        return true;
    VF2 nonSuppVF2(queryGraph, dataGraph);
    bool suppMatched = false;
    auto nonSuppPruneCallback = [&](std::map<int, int> &matchState) {
        return nonSuppPruneCheck(queryGraph,
                                 dataGraph,
                                 matchState,
                                 suppMatched);
    };
    auto nonSuppMatchCallback = [&](std::map<int, int> &matchState) {
        return nonSuppMatchCheck(queryGraph,
                                 dataGraph,
                                 matchState,
                                 suppMatched,
                                 suppValue,
                                 cntSupp,
                                 literalCheck);
    };
    return nonSuppVF2.vf2Engine(nonSuppMatchCallback,
                                nonSuppPruneCallback,
                                matchState);
}

//    对仅含有支点的子图进行匹配时使用的pruneCallback
//    实际上直接调用匿名函数
bool suppPruneCheck(Graph &queryGraph,
                    Graph &dataGraph,
                    std::map<int, int> &matchState) {
    return false;
}

// 默认不剪枝
bool defaultPruneCheck(std::map<int, int> &matchState) {
    return false;
}

//    进行支点匹配的代码
//    调用VF类
template<typename LiteralCheck>
bool suppMatch(Graph &queryGraph,
               Graph &dataGraph,
               std::set<int> &suppList,
               int &suppValue,
               int &cntSupp,
               LiteralCheck literalCheck
) {
    Graph suppSubGraph = generateSuppSubGraph(queryGraph, suppList);
    VF2 suppVF2(suppSubGraph, dataGraph);
    auto suppMatchCallback = [&](std::map<int, int> matchState) {
        return suppMatchCheck(queryGraph, dataGraph, matchState, suppValue, cntSupp, literalCheck);
    };

    return suppVF2.vf2Engine(suppMatchCallback,
                             defaultPruneCheck);
}

#endif //GFD_SUBGRAPHMATCH_H
